﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MessageWorkflow.Graph.Algorithm
{
    sealed class SubGraphAlgorithm<T>
    {
        private IGraph<T> _graph;
        private IGraph<T> _resultGraph;

        public SubGraphAlgorithm(IGraph<T> graph)
        {
            this._graph = graph;
        }

        /// <summary>
        /// Takes each value of the input set and builds a graph including only nodes specified
        /// </summary>
        public IGraph<T> BuildSubGraph(IEnumerable<T> nodes)
        {
            if (nodes == null)
                throw new ArgumentNullException("nodes");

            _resultGraph = new AdjacencyListGraph<T>();
            
            // first add all nessesary nodes to the resultGraph
            foreach (T node in nodes)
            {
                _resultGraph.Add(node);
            }

            // next, for each value, resolve the dependency chain
            foreach (T node in nodes)
            {
                FillTreeGraph(node, _graph.GetPredecessors(node), nodes);
            }

            return _resultGraph;
        }

        private void FillTreeGraph(T node, IEnumerable<T> predecessors, IEnumerable<T> nodes)
        {
            IEnumerable<T> existingPredecessors = from predecessor in predecessors
                                                  where nodes.Contains(predecessor)
                                                  select predecessor;

            _resultGraph.AddPredecessors(node, existingPredecessors);

            // next, go recursive to chain up higher level predecessors
            foreach (T Predecessor in predecessors)
            {
                FillTreeGraph(node, _graph.GetPredecessors(Predecessor), nodes);
            }
        }
    }
}
